package main.java.indi.zyj.classic150;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    class DoubleLinkedNode {
        int key;
        int val;
        DoubleLinkedNode prev, next;

        public DoubleLinkedNode() {}

        public DoubleLinkedNode(int _key, int _val) {
            this.key = _key;
            this.val = _val;
        }
    }


    Map<Integer, DoubleLinkedNode> caches = new HashMap<>();
    DoubleLinkedNode head, tail;
    int size;
    int capacity;

    public LRUCache(int capacity) {
        if (capacity <= 0) return;
        this.capacity = capacity;
        this.size = 0;
        head = new DoubleLinkedNode();
        tail = new DoubleLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    // 如果关键字 key 已经存在，则变更其数据值 value
    // 如果不存在，则向缓存中插入该组 key-value
    // 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字
    public void put(int key, int val) {
        DoubleLinkedNode doubleLinkedNode = caches.get(key);
        if (doubleLinkedNode == null) {
            DoubleLinkedNode newNode = new DoubleLinkedNode(key, val);
            caches.put(key, newNode);
            size++;
            if (size > capacity) {
                DoubleLinkedNode removeNode = removeTail();
                caches.remove(removeNode.key);
                addToHead(newNode);
                size--;
            }
        } else {
            doubleLinkedNode.val = val;
            moveToHead(doubleLinkedNode);
        }
    }

    //  如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
    public int get(int key) {
        DoubleLinkedNode dLinkedNode = caches.get(key);
        if (dLinkedNode == null) {
            return -1;
        }
        moveToHead(dLinkedNode);
        return dLinkedNode.val;
    }

    public void removeNode(DoubleLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public DoubleLinkedNode removeTail() {
        DoubleLinkedNode tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }

    public void addToHead(DoubleLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    public void moveToHead(DoubleLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }











}
